package com.work.daily;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * title :  按奇偶排序数组 II
 * link : https://leetcode-cn.com/problems/sort-array-by-parity-ii/
 * Created by suk on 2020/11/12
 */
public class D23_YQ_SortArrayByParityII_922_01 {

    public static void main(String[] args) {
        D23_YQ_SortArrayByParityII_922_01 d = new D23_YQ_SortArrayByParityII_922_01();
        int[] arrys = {560,986,192,424,997,829,897,843};
        System.out.println(Arrays.toString(d.sortArrayByParityII(arrys)));
    }

    public int[] sortArrayByParityII(int[] A) {

        Deque<int[]> stack = new ArrayDeque<>();

        for (int i = 0; i < A.length; i++) {
            // i和A[i] 不同时为奇数或偶数
            if (((i & 1) == 0 && (A[i] & 1) == 1) || ((i & 1) == 1 && (A[i] & 1) == 0)) {
                if (stack.isEmpty()) {
                    stack.offer(new int[]{i, A[i]});
                } else {
                    int[] nums = stack.peek();
                    if (((nums[0] & 1) == 0 && (i & 1) == 1) || ((nums[0] & 1) == 1 && (i & 1) == 0)) {
                        // 交换值
                        A[nums[0]] = A[i];
                        A[i] = nums[1];
                        stack.pop();
                    } else {
                        stack.offer(new int[]{i, A[i]});
                    }
                }
            }
        }
        return A;
    }
}
